package demo.DataStrucAndAlgo.Search;

import java.util.ArrayList;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/27-07-27-20:30
 * @Description：demo.DataStrucAndAlgo.Search     插值查找
 */
/*
插值查找 （二分查找的升级版）
    相较于二分查找，插值查找减少了递归次数
    改动：
        修改了mid的获取算法，二分查找中为(left+right)/2,
    插值查找中改进为left+(right-left)*(num-data[left])/(data[right]-data[left])
    主要是通过将要查找数据的大小与数列中最小数据的差值与整个数列插值进行比例计算，获取一个要查找数据的相对位置，从而快速的接近查找值的位置，进而减少查找次数
         修改了退出递归的条件：采用(left+right)/2计算mid值时，由于待查找值num也参与计算，当用户误输入（如：输入查找的数据不在数据数组范围且很大）时
    （right-left）*（num-data[left]）的值可能会变得巨大，从而计算得到的mid就会超出索引范围，导致下标越界。
    所以，在退出递归条件中，应加入对输入查询数据大小的范围判断(num<data[0]||num>data[data.length-1])

 */
public class insertSearch {
    public static void main(String[] args) {
//        int[] data = new int[100];
//        for (int i = 0; i < 100; i++) {
//            data[i] = i +1;
//        }
        int[] data = {2,3,6,7,10,13,24};
        System.out.println(insert_Search(data,0,data.length-1,100));
    }

    public static ArrayList<Integer> insert_Search(int[] data, int left, int right, int num ) {
        if(left > right || num <data[0] || num > data[data.length-1]){   //已遍历完数据，未找到匹配值，或不存在对应大小值，终止递归
            return new ArrayList<>();
        }
        int mid = left + (right - left) * (num - data[left])/(data[right] -data[left]);    //求中间下标
        int midVal = data[mid];
        if(num < midVal){
            return insert_Search(data,left,mid-1,num);    //向左递归查找
        }else if(num > midVal){
            return insert_Search(data,mid+1,right,num);    //向右递归查找
        }else{
            //找到了，返回索引数组
            ArrayList<Integer> list = new ArrayList<>();     //创建动态数组
            int temp = mid-1;
            while(temp >= 0 && data[temp] == num ){    //向左查找，是否有相同值
                list.add(temp);
                temp--;
            }
            list.add(mid);         //保存找到的中间值
            temp = mid +1;
            while(temp < data.length && data[temp] == num){     //向右查找是否有相同值
                list.add(temp);
                temp++;
            }
            return list;
        }
    }
}
